import java.util.TreeMap;
public class HashTable <K,V> {

    // 平均每个地址hash冲突需要调整的上界
    private static final int upperTol = 10;
    private static final int lowerTol = 2;
    // 初始容量
    private static final int initCapacity = 7;
    private TreeMap<K,V>[] hashtable;
    // hash表数组的容量
    private int M;

    private int size;

    public HashTable(int M){
        this.M = M;
        size = 0;
        hashtable = new TreeMap[M];
        for (int i = 0; i < M; i++) {
            hashtable[i] = new TreeMap<>();
        }
    }

    /**
     * 无参的构造函数，初始化一个默认大小的HashTable
     */
    public HashTable(){
        this(initCapacity);
    }

    /**
     * 求出传入key的hash值
     * @param key
     * @return
     */
    private int hash(K key){
        // 与16进制的7fffffff是为了求出负数的绝对值
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public int getSize(){
        return size;
    }

    public void add(K key, V value){
        TreeMap<K,V> map = hashtable[hash(key)];
        if (map.containsKey(key)){
            map.put(key, value);
        }else {
            map.put(key, value);
            size ++;
            // 扩容
            if (size >= upperTol * M){
                resize(2 * M);
            }
        }
    }

    public V remove(K key){
        TreeMap<K, V> map = hashtable[hash(key)];
        V ret = null;
        if (map.containsKey(key)){
            ret = map.remove(key);
            size --;

            // 缩容，最小缩至初始容量
            if (size < lowerTol * M && M / 2 >= initCapacity){
                resize(M / 2);
            }
        }
        return ret;
    }

    private void resize(int newM) {
        TreeMap<K, V>[] newHashTable = new TreeMap[newM];
        for (int i = 0; i < newM; i++) {
            newHashTable[i] = new TreeMap<>();
        }
        int oldM = M;
        // 为了根据新的HashTable重新计算hash值，这里重新将M赋值
        this.M = newM;
        for (int i = 0; i < oldM; i++) {
            TreeMap<K,V> map = hashtable[i];
            for (K key : map.keySet()){
                newHashTable[hash(key)].put(key,map.get(key));
            }

            this.hashtable = newHashTable;
        }
    }

    public void set(K key, V value){
        TreeMap<K, V> map = hashtable[hash(key)];
        if (!map.containsKey(key)){
            throw new IllegalArgumentException(key + "doesn't exist!");
        }
        map.put(key,value);
    }

    public boolean contains(K key){
        return hashtable[hash(key)].containsKey(key);
    }

    public V get(K key){
        return hashtable[hash(key)].get(key);
    }

}
